package club.xiaojiawei.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/14/22 4:38 PM
 * @question 257. 二叉树的所有路径
 * @description 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 * 叶子节点 是指没有子节点的节点。
 */
public class BinaryTreePaths257 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        left.right = new TreeNode(5);
        root.left = left;
        root.right = right;
        List<String> result = binaryTreePaths(root);
        System.out.println(result);
    }

    /**
     * 递归+DFS
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> result = new ArrayList<>();
        recursion(root, result, "");
        return result;
    }

    public static void recursion(TreeNode node, List<String> list, String s){
        if (node == null){
            return;
        }
        if (s.length() != 0){
            s += "->";
        }
        s += node.val;
        if (node.right !=null || node.left != null){
            recursion(node.left, list, s);
            recursion(node.right, list, s);
        }else if (s.length() > 0){
            list.add(s);
        }
    }

    /**
     * 官方-BFS+队列
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths2(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();
        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();
            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }
                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }

    /**
     * 民间-DFS+递归(路径用List数组代替String)
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths3(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;
        List<Integer> Path = new ArrayList<>();
        travel(root, Path, result);
        return result;
    }
    public static void travel(TreeNode root, List<Integer> Path, List<String> result) {
        Path.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<Path.size()-1; i++) {
                sb.append(Path.get(i)).append("->");
            }
            sb.append(Path.get(Path.size()-1));
            result.add(sb.toString());
        }
        if (root.left != null) {
            travel(root.left, Path, result);
            Path.remove(Path.size() - 1);
        }
        if (root.right != null) {
            travel(root.right, Path, result);
            Path.remove(Path.size() - 1);
        }
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
